#include <iostream>
#include <string>
#include <vector>
using namespace std;

int edit_distance(const string& s1, const string& s2)
{
	vector<vector<int> > v;
	for(int i=0;i<=s1.size();i++)
		v.push_back(vector<int>(s2.size()+1));
	
	// init
	for(int i=0;i<=s1.size();i++)
		v[i][0]=i;
	for(int i=0;i<=s2.size();i++)
		v[0][i]=i;
	// it
	for(int i=1;i<=s1.size();i++)
		for(int j=1;j<=s2.size();j++)
			v[i][j]=min(min(v[i][j-1]+1, v[i-1][j]+1),
				v[i-1][j-1]+
				(s1[i-1]==s2[j-1] ? 0 : 1));
	return v[s1.size()][s2.size()];
}

int main()
{
	cout<< edit_distance("abc","abcd")<<endl; // 1
	cout<< edit_distance("abcd","ascd")<<endl; // 1
}